//给定一个可包含重复数字的序列，返回所有不重复的全排列。 
//
// 示例: 
//
// 输入: [1,1,2]
//输出:
//[
//  [1,1,2],
//  [1,2,1],
//  [2,1,1]
//] 
// Related Topics 回溯算法 
// 👍 381 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

//Java：全排列 II
public class P47PermutationsIi {

    /**
     * 思路：参考第46题，加上判重复的代码即可，即可实现
     *
     * 执行用时： 2 ms , 在所有 Java 提交中击败了 75.96% 的用户 内存消耗： 40.5 MB , 在所有 Java 提交中击败了 46.26% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        private List<List<Integer>> list = new ArrayList<>();

        public List<List<Integer>> permuteUnique(int[] nums) {
            if (nums.length != 0) {
                Arrays.sort(nums);
                boolean[] used = new boolean[nums.length];
                dfs(nums, used, new Stack<>(), 0);
            }
            return list;
        }

        private void dfs(int[] nums, boolean[] used, Stack<Integer> path, int i) {
            if (path.size() == nums.length) {
                list.add(new ArrayList<>(path));
                return;
            }

            for (int start = 0; start < nums.length; start++) {
                // 如果多建一个数组来存是否使用过，而不是用 contains 方法，速度可能会快一点
                if (used[start]) {
                    continue;
                }

                // 判重复 【这是最难的】
                if (start > 0 && nums[start] == nums[start - 1] && !used[start - 1]) {
                    continue;
                }


                used[start] = true;
                path.push(nums[start]);

                dfs(nums, used, path, start+1);

                path.pop();
                used[start] = false;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P47PermutationsIi().new Solution();
        int[] nums = new int[]{1, 1, 1, 3};
        solution.permuteUnique(nums);
        // TO TEST
    }

}